package robinson.util;

import java.util.Vector;

public class AlgorithmUtil {
	public static int compareIndex = 0;
	public static int loopIndex = 0;
	public static int moveIndex = 0;

	public static int[] bubbleSort(int[] disorderedArray) {
		loopIndex = 0;
		compareIndex = 0;
		moveIndex = 0;
		int temp;
		for (int i = 0; i < disorderedArray.length; i++) {
			loopIndex++;
			for (int j = disorderedArray.length - 1; j > i; j--) {
				loopIndex++;
				compareIndex++;
				if (disorderedArray[j] < disorderedArray[j - 1]) {
					moveIndex++;
					temp = disorderedArray[j];
					disorderedArray[j] = disorderedArray[j - 1];
					disorderedArray[j - 1] = temp;
				}
			}
		}
		return disorderedArray;
	}

	public static int[] insertionSort(int[] disorderedArray) {
		loopIndex = 0;
		compareIndex = 0;
		moveIndex = 0;
		int temp;
		for (int i = 1; i < disorderedArray.length; i++) {
			loopIndex++;
			temp = disorderedArray[i];
			int j = i - 1;
			while (j >= 0 && temp < disorderedArray[j]) {
				loopIndex++;
				compareIndex++;
				disorderedArray[j + 1] = disorderedArray[j];
				moveIndex++;
				j--;
			}
			disorderedArray[j + 1] = temp;
			moveIndex++;
		}
		return disorderedArray;
	}

	private static int[] insertionSortSubShellSort(int[] disorderedArray, int d) {
		int temp;
		for (int i = d; i < disorderedArray.length; i++) {
			loopIndex++;
			int j = i - d;
			temp = disorderedArray[i];
			while (j >= 0 && temp < disorderedArray[j]) {
				loopIndex++;
				compareIndex++;
				disorderedArray[j + d] = disorderedArray[j];
				moveIndex++;
				j = j - d;
			}
			disorderedArray[j + d] = temp;
			moveIndex++;
		}
		return disorderedArray;
	}

	public static int[] shellSort(int[] disorderedArray) {
		loopIndex = 0;
		compareIndex = 0;
		moveIndex = 0;
		int d = disorderedArray.length / 2;
		while (d > 0) {
			loopIndex++;
			disorderedArray = insertionSortSubShellSort(disorderedArray, d);
			moveIndex++;
			d = d / 2;
		}
		return disorderedArray;
	}

	private static int parittion(int[] disorderedArray, int low, int high) {
		int pivot = disorderedArray[low];
		while (low < high) {
			loopIndex++;
			compareIndex++;
			while (low < high && disorderedArray[high] >= pivot) {
				loopIndex++;
				compareIndex = compareIndex + 2;
				high--;
			}
			if (low < high) {
				compareIndex++;
				disorderedArray[low++] = disorderedArray[high];
				moveIndex++;
			}
			while (low < high && disorderedArray[low] <= pivot) {
				loopIndex++;
				compareIndex = compareIndex + 2;
				low++;
			}
			if (low < high) {
				compareIndex++;
				disorderedArray[high--] = disorderedArray[low];
				moveIndex++;
			}
		}
		disorderedArray[low] = pivot;
		moveIndex++;
		return low;
	}

	public static int[] quickSort(int[] disorderedArray, int low, int high) {

		int pivotpos;
		if (low < high) {
			compareIndex++;
			pivotpos = parittion(disorderedArray, low, high);
			quickSort(disorderedArray, low, pivotpos - 1);
			quickSort(disorderedArray, pivotpos + 1, high);
		}

		return disorderedArray;
	}

	public static int[] straightSelectionSort(int[] disorderedArray) {
		loopIndex = 0;
		compareIndex = 0;
		moveIndex = 0;
		int temp;
		for (int i = 0; i < disorderedArray.length; i++) {
			loopIndex++;
			for (int j = i + 1; j < disorderedArray.length; j++) {
				loopIndex++;
				compareIndex++;
				if (disorderedArray[i] > disorderedArray[j]) {
					temp = disorderedArray[i];
					disorderedArray[i] = disorderedArray[j];
					disorderedArray[j] = temp;
					moveIndex++;
				}
			}
		}
		return disorderedArray;
	}

	public static int[] heapSort(int[] disorderedArray) {
		loopIndex = 0;
		compareIndex = 0;
		moveIndex = 0;
		int heapSize = disorderedArray.length - 1;
		int temp;
		buildMaxHeap(disorderedArray, heapSize);
		for (int j = heapSize; j >= 1; j--) {
			loopIndex++;
			temp = disorderedArray[j];
			disorderedArray[j] = disorderedArray[0];
			disorderedArray[0] = temp;
			moveIndex++;
			maxHeapify(disorderedArray, 0, j - 1);
		}

		return disorderedArray;
	}

	private static void buildMaxHeap(int[] disorderedArray, int heapSize) {
		for (int i = HeapArrayUtil.getParentIndex(heapSize); i >= 0; i--) {
			loopIndex++;
			maxHeapify(disorderedArray, i, heapSize);

		}
	}

	private static void maxHeapify(int[] disorderedArray, int index,
			int heapSize) {
		int LC = HeapArrayUtil.getLeftChildIndex(index);
		int RC = LC + 1;
		int maxKeyIndex = index;
		int temp;
		if (LC <= heapSize
				&& disorderedArray[maxKeyIndex] < disorderedArray[LC]) {
			maxKeyIndex = LC;
		}
		compareIndex++;
		if (RC <= heapSize
				&& disorderedArray[maxKeyIndex] < disorderedArray[RC]) {
			maxKeyIndex = RC;
		}
		compareIndex++;
		if (maxKeyIndex != index) {
			// swap disorderedArray[maxKeyIndex],disorderedArray[index]
			temp = disorderedArray[maxKeyIndex];
			disorderedArray[maxKeyIndex] = disorderedArray[index];
			disorderedArray[index] = temp;
			moveIndex++;
			maxHeapify(disorderedArray, maxKeyIndex, heapSize);
		}
		compareIndex++;
	}

	public static int[] mergeSort(int[] disorderedArray) {
		loopIndex = 0;
		compareIndex = 0;
		moveIndex = 0;
		for (int length = 1; length < disorderedArray.length; length *= 2) {
			loopIndex++;
			mergePass(disorderedArray, length);
		}

		return disorderedArray;
	}

	private static void mergePass(int[] disorderedArray, int length) {
		int n = disorderedArray.length - 1;
		int i;
		for (i = 0; i + 2 * length <= n; i = i + 2 * length) {
			loopIndex++;
			meger(disorderedArray, i, i + length - 1, i + 2 * length - 1);

		}
		if (i + length - 1 < n) {// the last file is less than length
			meger(disorderedArray, i, i + length - 1, n);
		}
		// if i<=n and i+lenght-1>=n, that is
		// disorderedArray[i+length,i+2*length-1] will out of range, so last
		// group only have one file
	}

	private static void meger(int[] disorderedArray, int low, int middleLeft,
			int high) {
		int i = low;
		int j = middleLeft + 1;
		int k = 0;
		int[] tempArray = new int[high - low + 1];

		while (i <= middleLeft && j <= high) {
			loopIndex++;
			compareIndex++;
			moveIndex++;
			tempArray[k++] = (disorderedArray[i] <= disorderedArray[j]) ? disorderedArray[i++]
					: disorderedArray[j++];
		}
		while (i <= middleLeft) {
			loopIndex++;
			moveIndex++;
			tempArray[k++] = disorderedArray[i++];// if the second array has
													// been check over,but not
													// the first one
		}
		while (j <= high) {// if the first array has been check over,but not the
							// second one
			loopIndex++;
			moveIndex++;
			tempArray[k++] = disorderedArray[j++];
		}
		for (k = 0, i = low; k < tempArray.length; k++, i++) {
			loopIndex++;
			moveIndex++;
			disorderedArray[i] = tempArray[k];// copy the ordered array to the
												// old array
		}
	}

	public static int[] radixSort(int[] disorderedArray,int radix,int maxDigit) {
		int[][] tempArray=new int[radix-1][disorderedArray.length-1];
		for(int i=0;i<=maxDigit;i++){
			box(tempArray,disorderedArray,radix,i);
		}
		
		return disorderedArray;
	}

	private static void box(int[][] tempArray,int[] disorderedArray,int radix,int digit) {
		int integerPart;
		int quotient;
		for(int i=0;i<disorderedArray.length;i++){
			integerPart= disorderedArray[i]/(radix^digit);
			quotient=integerPart% radix;
			int j=0;
			while(tempArray[quotient][j]>0){
				j++;
			}			
			tempArray[quotient][j]=disorderedArray[i];
			
		}
		
		for(int i=0;i<radix;i++){
			int j=0;
			int k=0;
			while(tempArray[i][j]>0){
				disorderedArray[k++]=tempArray[i][j];
				tempArray[i][j]=0;
				j++;
			}
			
		}
		
	}

	public static void printArray(int[] array) {

		System.out.println("Array Items are:");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ", ");
		}
		System.out.println();
		System.out.println("loop Index: " + loopIndex);
		System.out.println("compare Index: " + compareIndex);
		System.out.println("move Index: " + moveIndex);
	}
}
